iT邦幫忙

2026 iThome 鐵人賽
DAY 26
0
自我挑戰組

韌體工程師的不只 0x10 個問題系列 第 26 篇

Day 26－死結與解決方式

18th鐵人賽
121 瀏覽

  • 分享至 

  • xImage
    •  

前面介紹了互斥鎖可以避免資料競爭，但如果複數個執行緒都把持著某些資源、卻也都同時在等待其他執行緒手上的資源，就會形成「死結（deadlock）」。

死結形成的四個條件

這邊簡單帶過理論上形成死結四個應同時成立的「科夫曼（Coffman）條件」：

  1. 互斥（mutual exclusion）：資源不能給多執行緒同時共享。
  2. 持有並等待（hold and wait）：執行緒持有部分資源，但同時間也在等待其他執行緒手上的資源。
  3. 不可搶占（no preemption）：不能把別的執行緒資源搶走，只能等人家主動釋放。
  4. 循環等待（circular wait）：每個執行緒都持有特定資源，卻也在等待其他執行緒的資源。

死結範例

以下程式碼將形成死結：

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>

std::mutex mtxA;
std::mutex mtxB;

// 第一個執行緒：持有 A 鎖、等待 B 鎖
void threadOneWorker() {
    std::cout << "Thread 1: Trying to lock A...\n";
    std::unique_lock<std::mutex> lockA(mtxA);  // 把 A 鎖拿走
    std::cout << "Thread 1: Locked A successfully!\n";

    // 小睡片刻，給第二個執行緒足夠的時間去拿 B 鎖
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
    
    // A 鎖想要去取 B 鎖
    std::cout << "Thread 1: Trying to lock B...\n";
    std::unique_lock<std::mutex> lockB(mtxB); // B 鎖已被第二個執行緒拿走，所以第一個執行緒永遠等不到
    std::cout << "Thread 1: Locked B successfully!\n";
}

// 第一個執行緒：持有 B 鎖、等待 A 鎖
void threadTwoWorker() {
    std::cout << "Thread 2: Trying to lock B...\n";
    std::unique_lock<std::mutex> lockB(mtxB);  // 把 B 鎖拿走
    std::cout << "Thread 2: Locked B successfully!\n";

    // 小睡片刻，給第一個執行緒足夠的時間去拿 A 鎖
    std::this_thread::sleep_for(std::chrono::milliseconds(50));

    std::cout << "Thread 2: Trying to lock A...\n";
    std::unique_lock<std::mutex> lockA(mtxA); // A 鎖已被第一個執行緒拿走，所以第二個執行緒永遠等不到
    std::cout << "Thread 2: Locked A successfully!\n";
}

int main() {
    std::thread t1(threadOneWorker);
    std::thread t2(threadTwoWorker);

    t1.join();
    t2.join();

    // 第一個執行緒 t1 持有 A 鎖、等待 B 鎖
    // 第二個執行緒 t2 持有 B 鎖、等待 A 鎖
    // 兩執行緒僵持不下，無法執行到這裡
    std::cout << "Program finished smoothly.\n"; 
    return 0;
}

在此範例中：

  • 第一個執行緒 t1 抓到 A 鎖後，還需要 B 鎖，但 B 鎖被第二個執行緒 t2 抓著不放。
  • 第二個執行緒 t2 抓到 B 鎖後，還需要 A 鎖，但 A 鎖被第一個執行緒 t1 抓著不放。

兩執行緒僵持不下，因此就卡住、形成「死結」，執行結果如下：

Thread 2: Trying to lock B...
Thread 2: Locked B successfully!
Thread 1: Trying to lock A...
Thread 1: Locked A successfully!
Thread 2: Trying to lock A...
Thread 1: Trying to lock B...

前四行兩執行緒都有順利拿到鎖，第五行開始則各自拿不到鎖，直接卡住，永遠無法抵達 Program finished smoothly。

死結解法

既然形成死結要同時滿足四個科夫曼條件，那只要把其中一個條件拿掉，就可以解開死結。

手動調整

四個條件中，最容易打破的是「循環等待」，讓每個執行緒都依照固定順序取得資源，避免兩執行緒各自取了某些資源、卻又都在等待對方手上的資源。

上例若改成「兩執行緒都先取 A 鎖再取 B 鎖」，便成解開死結，兩執行緒都能取得 A 鎖與 B 鎖：

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>

std::mutex mtxA;
std::mutex mtxB;

// 第一個執行緒不變，先拿 A 鎖再拿 B 鎖
void threadOneWorker() {
    std::cout << "Thread 1: Trying to lock A...\n";
    std::unique_lock<std::mutex> lockA(mtxA);

    std::this_thread::sleep_for(std::chrono::milliseconds(50));

    std::cout << "Thread 1: Trying to lock B...\n";
    std::unique_lock<std::mutex> lockB(mtxB);
    std::cout << "Thread 1: Locked both successfully!\n";
}

// 第二個執行緒也改成先拿 A 鎖再拿 B 鎖
void threadTwoWorker() {
    std::cout << "Thread 2: Trying to lock A...\n"; // 改先拿 A 鎖
    std::unique_lock<std::mutex> lockA(mtxA);

    std::this_thread::sleep_for(std::chrono::milliseconds(50));

    std::cout << "Thread 2: Trying to lock B...\n"; // 再拿 B 鎖
    std::unique_lock<std::mutex> lockB(mtxB);
    std::cout << "Thread 2: Locked both successfully!\n";
}

int main() {
    std::thread t1(threadOneWorker);
    std::thread t2(threadTwoWorker);

    t1.join();
    t2.join();

    // 這行可成功顯示
    std::cout << "Program finished smoothly.\n"; 
    return 0;
}

執行結果如下：

Thread 1: Trying to lock A...
Thread 2: Trying to lock A...
Thread 1: Trying to lock B...
Thread 1: Locked both successfully!
Thread 2: Trying to lock B...
Thread 2: Locked both successfully!
Program finished smoothly.

說明如下：

  1. 第一個執行緒取得 A 鎖資源。
  2. 第二個執行緒也想取得 A 鎖，但 A 鎖被第一個執行緒霸佔，只好等釋出。
  3. 第一個執行緒取得 B 鎖資源。
  4. 第一個執行緒成功取得兩個鎖後，便釋放兩個鎖的資源；排隊中的第二個執行緒順利取得在第 2. 步等待的 A 鎖資源。
  5. 第二個執行緒也取得 B 鎖資源。
  6. 第二個執行緒成功取得兩個鎖後，也會釋放兩鎖的資源。
  7. 程式執行結束。

使用 std::scoped_lock

這是 C++ 17 開始推出的防死結鎖，可以把兩個以上的互斥鎖統一管理，讓任一執行緒「持有全部資源」或「沒有全部資源」，而不會「拿了某些資源、卻在等待其他資源」，也就避免了死結的可能性。寫法如下：

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>

std::mutex mtxA;
std::mutex mtxB;

void threadOneWorker() {
    std::cout << "Thread 1: Safely locking A and B via scoped_lock...\n";
    
    // 第一個執行緒把兩個互斥鎖都放進 scoped_lock
    std::scoped_lock lock(mtxA, mtxB); 

    std::cout << "Thread 1: Locked both successfully!\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
} // 離開大括號，scoped_lock 自動把 mtxA 和 mtxB 兩個鎖釋放

void threadTwoWorker() {
    std::cout << "Thread 2: Safely locking B and A via scoped_lock...\n";
    
    // 第二個執行緒也把兩個互斥鎖都放進 scoped_lock
    std::scoped_lock lock(mtxB, mtxA); 

    std::cout << "Thread 2: Locked both successfully!\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
} // 離開大括號，scoped_lock 自動把 mtxB 和 mtxA 兩個鎖釋放

int main() {
    std::thread t1(threadOneWorker);
    std::thread t2(threadTwoWorker);
    t1.join();
    t2.join();

    std::cout << "Program finished smoothly.\n"; 
    return 0;
}

執行結果如下，可見兩個執行緒沒有互相卡住對方，有辦法執行到最後的 Program finished smoothly：

Thread 1: Safely locking A and B via scoped_lock...
Thread 1: Locked both successfully!
Thread 2: Safely locking B and A via scoped_lock...
Thread 2: Locked both successfully!
Program finished smoothly.

補充：C++ 17 以前使用的 std::lock

在 C++ 17 以前若要避免死結，則要先上 std::defer_lock 延遲上鎖後，再都丟進 std::lock 如下：

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>

std::mutex mtxA;
std::mutex mtxB;

void threadOneWorker() {
    std::cout << "Thread 1: Safely locking A and B via std::lock...\n";
    
    // 先放進 defer_lock 延遲上鎖
    std::unique_lock<std::mutex> lockA(mtxA, std::defer_lock);
    std::unique_lock<std::mutex> lockB(mtxB, std::defer_lock);

    // 把兩個鎖同時丟給 std::lock，由演算法保證不發生死結
    std::lock(lockA, lockB); 

    std::cout << "Thread 1: Locked both successfully!\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
} // 離開大括號，lockA 和 lockB 自動解鎖

void threadTwoWorker() {
    std::cout << "Thread 2: Safely locking B and A via std::lock...\n";
    
    // 一樣先放進 defer_lock 延遲上鎖
    std::unique_lock<std::mutex> lockB(mtxB, std::defer_lock);
    std::unique_lock<std::mutex> lockA(mtxA, std::defer_lock);

    // 把兩個鎖同時丟給 std::lock，由演算法保證不發生死結
    std::lock(lockB, lockA); 

    std::cout << "Thread 2: Locked both successfully!\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
} // 離開大括號，lockB 和 lockA 自動解鎖

int main() {
    std::thread t1(threadOneWorker);
    std::thread t2(threadTwoWorker);
    t1.join(); t2.join();

    std::cout << "Program finished smoothly.\n"; 
    return 0;
}

執行結果如下：

Thread 1: Safely locking A and B via std::lock...
Thread 2: Safely locking B and A via std::lock...
Thread 1: Locked both successfully!
Thread 2: Locked both successfully!
Program finished smoothly.

參考資料

  1. Introduction of Deadlock in Operating System (GeeksforGeeks)
  2. std::lock (cppreference)
  3. std::scoped_lock (cppreference)

上一篇
Day 25－解決資料競爭，不能解決競賽條件
下一篇
Day 27－活鎖與飢餓
系列文
韌體工程師的不只 0x10 個問題 共 31 篇
  1. 27
    Day 27－活鎖與飢餓
  2. 28
    Day 28－記憶體模型
  3. 29
    Day 29－用 async / promise + future 進行非同步處理
  4. 30
    Day 30－執行緒池
  5. 31
    Day 31－回顧
完整目錄
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
500 組
團體組數
22 組
累計文章數
5445 篇
最後報名日
9/15
iT+看影片追技術 看影片追技術 看更多
熱門tag
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 17th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 18th鐵人賽 python 2017鐵人賽 windows php c# linux windows server css
熱門問題
熱門回答
熱門文章
IT邦幫忙